﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Sort
{
    class QSort
    {
        static public void Sort1(int[] arr, int beg, int end)
        {
            if (end - beg < 1)
                return;

            if(end == beg+1)
            {
                if (arr[beg] > arr[end])
                    lib.Swap<int>(arr, beg, end);
                return;
            }

            int current = beg+1;
            int midVal = arr[beg];

            for(int i = beg+1; i<=end; i++)
            {
                if(arr[i] < midVal)
                {
                    lib.Swap<int>(arr, i, current);
                    current++;
                }
            }
            lib.Swap<int>(arr, beg, current-1);

            Sort1(arr, beg, current - 2);
            Sort1(arr, current, end);
        }

        static public void Sort2(int[] arr, int beg, int end)
        {
            if (end - beg < 1)
                return;

            if (end == beg + 1)
            {
                if (arr[beg] > arr[end])
                    lib.Swap<int>(arr, beg, end);
                return;
            }

            int midVal = arr[beg];
            int minIdx = beg+1;
            int maxIdx = end;

            while(minIdx < maxIdx)
            {
                while (minIdx < maxIdx && arr[minIdx] < midVal)
                    minIdx++;

                while (minIdx < maxIdx && arr[maxIdx] >= midVal)
                    maxIdx--;

                if (minIdx != maxIdx)
                    lib.Swap<int>(arr, minIdx, maxIdx);
            }

            if (arr[minIdx] >= midVal)
            {
                lib.Swap<int>(arr, minIdx - 1, beg);
                Sort2(arr, beg, minIdx - 2);
                Sort2(arr, minIdx, end);
            }
            else
            {
                lib.Swap<int>(arr, minIdx, beg);
                Sort2(arr, beg, minIdx - 1);
                Sort2(arr, minIdx+1, end);
            }
        }

        static public void Sort3(int[] arr, int beg, int end)
        {
            if (beg >= end)
                return;

            if (end == beg + 1)
            {
                if (arr[beg] > arr[end])
                    lib.Swap<int>(arr, beg, end);
                return;
            }

            int first = beg;
            int last = end;
            int key = arr[beg];

            while (last > first)
            {
                if (arr[last] > key)
                {
                    last--;
                    continue;
                }

                if (arr[first] <= key)
                {
                    first++;
                    continue;
                }
                lib.Swap(arr, first, last);
            }
            lib.Swap(arr, beg, first);

            Sort3(arr, beg, first - 1);
            Sort3(arr, first + 1, end);
        }
    }
}
